Pseudocodeword-Free Criterion for Codes with Cycle-Free Tanner Graph

摘要

Iterative decoding and linear programming decoding are guaranteed to convergeto the maximum-likelihood codeword when the underlying Tanner graph iscycle-free. Therefore, cycles are usually seen as the culprit of low-densityparity-check (LDPC) codes. In this paper, we argue in the context of graphcover pseudocodeword that, for a code that permits a cycle-free Tanner graph,cycles have no effect on error performance as long as they are a part ofredundant rows. Specifically, we characterize all parity-check matrices thatare pseudocodeword-free for such class of codes.